"""
用栈来模拟一个队列，要求实现队列的两个基本操作：入队、出队。


-- 栈是先入后出，队列是先入先出，用栈没办法实现队列吧？


提示，用一个栈肯定是没办法实现队列的，但如果我们有两个栈呢？


-- 既然拥有两个栈，那么可以让其中一个栈作为队列的入口，负责插入新元素；
-- 另一个栈作为队列的出口，负责移除老元素。
"""


class StackQueue:
    def __init__(self):
        self.stackA = []
        self.stackB = []

    def en_queue(self, element):
        """入队
        时间复杂度是O（1）
        """
        self.stackA.append(element)

    def de_queue(self):
        """出队
        如果涉及栈A和栈B的元素迁移，那么一次出队的时间复杂度是O（n）；如果不用迁移，时间复杂度是O（1）
        涉及一个新的概念，叫作均摊时间复杂度。需要元素迁移的出队操作只是少数情况，并且不可能连续出现，其后的大多数出队操作都不需要元素迁移
        所以把时间均摊到每一次出队操作上面，其时间复杂度是O（1）。
        """
        if len(self.stackB) == 0:
            if len(self.stackA) == 0:
                raise Exception("栈已经空了！")
            self.transfer()
        return self.stackB.pop()

    def transfer(self):
        while len(self.stackA) > 0:
            self.stackB.append(self.stackA.pop())


if __name__ == '__main__':
    stack_queue = StackQueue()
    stack_queue.en_queue(1)
    stack_queue.en_queue(2)
    stack_queue.en_queue(3)
    print(stack_queue.de_queue())
    print(stack_queue.de_queue())
    stack_queue.en_queue(4)
    print(stack_queue.de_queue())
    print(stack_queue.de_queue())
